package org.hhchat.leetcode.tree;

import org.hhchat.leetcode.dataStruct.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class code107_easy {
    static class Solution {
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
            List<List<Integer>> lists = new ArrayList<>();
            if(root==null){
                return lists;
            }
            Queue<Node> queue = new LinkedList<>();
            queue.offer(new Node(root,0));
            while(!queue.isEmpty()){
                Node node = queue.poll();
                TreeNode treeNode = node.treeNode;
                TreeNode leftNode = null;
                TreeNode rightNode = null;
                if(treeNode.left!=null){
                    leftNode = treeNode.left;
                    queue.add(new Node(leftNode, node.level + 1));
                }
                if(treeNode.right!=null){
                    rightNode = treeNode.right;
                    queue.add(new Node(rightNode, node.level + 1));
                }
                if(node.level>=lists.size()){
                    lists.add(new ArrayList<>());
                }
                lists.get(node.level).add(node.treeNode.val);
            }
            return reverseList(lists);
        }

        public List<List<Integer>> reverseList (List<List<Integer>> lists){
            List<List<Integer>> result = new ArrayList<>();
            for(int i=0;i<lists.size();i++){
                result.add(lists.get(lists.size()-i-1));
            }
            return result;
        }

         class Node{
             TreeNode treeNode;
             int level;

             Node(TreeNode treeNode, int level) {
                this.treeNode = treeNode;
                this.level = level;
            }
        }
    }
    public static void main(String[] args){

    }
}


/**
 * leetcode 解法，通过递归将level传下去
 * https://leetcode.com/problems/binary-tree-level-order-traversal-ii/discuss/
 */

//public class Solution {
//    public List<List<Integer>> levelOrderBottom(TreeNode root) {
//        List<List<Integer>> wrapList = new LinkedList<List<Integer>>();
//        levelMaker(wrapList, root, 0);
//        return wrapList;
//    }
//
//    public void levelMaker(List<List<Integer>> list, TreeNode root, int level) {
//        if(root == null) return;
//        if(level >= list.size()) {
//            list.add(0, new LinkedList<Integer>());
//        }
//        levelMaker(list, root.left, level+1);
//        levelMaker(list, root.right, level+1);
//        list.get(list.size()-level-1).add(root.val);
//    }
//}